{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coloring A Border"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: colorBorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #边界着色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的整数矩阵 <code>grid</code> ，表示一个网格。另给你三个整数&nbsp;<code>row</code>、<code>col</code> 和 <code>color</code> 。网格中的每个值表示该位置处的网格块的颜色。</p>\n",
    "\n",
    "<p>如果两个方块在任意 4 个方向上相邻，则称它们&nbsp;<strong>相邻 </strong>。</p>\n",
    "\n",
    "<p>如果两个方块具有相同的颜色且相邻，它们则属于同一个 <strong>连通分量</strong> 。</p>\n",
    "\n",
    "<p><strong>连通分量的边界</strong><strong> </strong>是指连通分量中满足下述条件之一的所有网格块：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻</li>\n",
    "\t<li>在网格的边界上（第一行/列或最后一行/列）</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你使用指定颜色&nbsp;<code>color</code> 为所有包含网格块&nbsp;<code>grid[row][col]</code> 的 <strong>连通分量的边界</strong> 进行着色。</p>\n",
    "\n",
    "<p>并返回最终的网格&nbsp;<code>grid</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1],[1,2]], row = 0, col = 0, color = 3\n",
    "<strong>输出：</strong>[[3,3],[3,2]]</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3\n",
    "<strong>输出：</strong>[[1,3,3],[2,3,3]]</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2\n",
    "<strong>输出：</strong>[[2,2,2],[2,1,2],[2,2,2]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j], color &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= row &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= col &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coloring-a-border](https://leetcode.cn/problems/coloring-a-border/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coloring-a-border](https://leetcode.cn/problems/coloring-a-border/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[1,2]]\\n0\\n0\\n3', '[[1,2,2],[2,3,2]]\\n0\\n1\\n3', '[[1,1,1],[1,1,1],[1,1,1]]\\n1\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        target=grid[row][col]\n",
    "        vis=set()\n",
    "        vis.add((row,col))\n",
    "        q=deque([(row,col)])\n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for x,y in (i+1,j),(i-1,j),(i,j-1),(i,j+1):\n",
    "                if (x,y) not in vis:\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y]==target:\n",
    "                        vis.add((x,y))\n",
    "                        q.append((x,y))\n",
    "                    else:\n",
    "                        grid[i][j]=color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if grid[i][j] == c:\n",
    "                    grid[i][j] = 0\n",
    "                    if dfs(i + 1, j) | dfs(i - 1, j) | dfs(i, j + 1) | dfs(i, j - 1) or not i % (m - 1) or not j % (n - 1):\n",
    "                        board.append((i, j))\n",
    "                    grid[i][j] = c\n",
    "                return grid[i][j] != c and grid[i][j] != 0\n",
    "            return False\n",
    "\n",
    "\n",
    "        m, n, c, board = len(grid), len(grid[0]), grid[row][col], []\n",
    "        dfs(row, col)\n",
    "        for i, j in board:\n",
    "            grid[i][j] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Cell:\n",
    "    def __init__(self, x, y, value, row, col) -> None:\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.value = value\n",
    "        self.is_board = False  # 是否联通份量\n",
    "        if self.x == 0 or self.y == 0 or self.x == row or self.y == col:\n",
    "            self.is_edge = True\n",
    "        else:\n",
    "            self.is_edge = False\n",
    "        self.is_vistor = False\n",
    "\n",
    "    def up(self, maps):\n",
    "        up_cell = maps.get((self.x - 1, self.y))\n",
    "        if up_cell and up_cell.value == self.value:\n",
    "            if up_cell.is_vistor:\n",
    "                return False\n",
    "            return up_cell.start(maps)\n",
    "        return True\n",
    "\n",
    "    def down(self, maps):\n",
    "        down_cell = maps.get((self.x + 1, self.y))\n",
    "        if down_cell and down_cell.value == self.value:\n",
    "            if down_cell.is_vistor:\n",
    "                return False\n",
    "            return down_cell.start(maps)\n",
    "        return True\n",
    "\n",
    "    def left(self, maps):\n",
    "        left_cell = maps.get((self.x, self.y - 1))\n",
    "        if left_cell and left_cell.value == self.value:\n",
    "            if left_cell.is_vistor:\n",
    "                return False\n",
    "            return left_cell.start(maps)\n",
    "        return True\n",
    "\n",
    "    def right(self, maps):\n",
    "        right_cell = maps.get((self.x, self.y + 1))\n",
    "        if right_cell and right_cell.value == self.value:\n",
    "            if right_cell.is_vistor:\n",
    "                return False\n",
    "            return right_cell.start(maps)\n",
    "        return True\n",
    "\n",
    "    def start(self, maps):\n",
    "        self.is_vistor = True\n",
    "        if any([self.up(maps), self.down(maps), self.left(maps), self.right(maps)]):\n",
    "            self.is_board = True\n",
    "        return False\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(\n",
    "            (self.x, self.y, \" is_edge: \", self.is_edge, \" is_board: \", self.is_board)\n",
    "        )\n",
    "\n",
    "    __repr__ = __str__\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(\n",
    "        self, grid: List[List[int]], row: int, col: int, color: int\n",
    "    ) -> List[List[int]]:\n",
    "        width = len(grid[0]) - 1\n",
    "        height = len(grid) - 1\n",
    "        cells = dict()\n",
    "        for x, rows in enumerate(grid):\n",
    "            for y, value in enumerate(rows):\n",
    "                cells[(x, y)] = Cell(x, y, value, height, width)\n",
    "        cell = cells.get((row, col))\n",
    "        cell.start(cells)\n",
    "        result = []\n",
    "        for x, rows in enumerate(grid):\n",
    "            result_line = []\n",
    "            for y, value in enumerate(rows):\n",
    "                cell = cells.get((x, y))\n",
    "                if cell.is_board:\n",
    "                    result_line.append(color)\n",
    "                else:\n",
    "                    result_line.append(cell.value)\n",
    "            result.append(result_line)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        # m,n=len(grid),len(grid[0])\n",
    "        # a = [[False]*n for _ in range(m)]\n",
    "\n",
    "        # border = []\n",
    "        # ori_color = grid[row][col]\n",
    "\n",
    "        # a[row][col]=True\n",
    "        # def dfs(x,y):\n",
    "        #     isborder=False\n",
    "        #     dirs = [[-1,0],[1,0],[0,1],[0,-1]]\n",
    "\n",
    "        #     for dx,dy in dirs:\n",
    "        #         nx,ny=x+dx,y+dy\n",
    "        #         if not (0<=nx<m and 0<=ny<n and grid[nx][ny]==ori_color):\n",
    "        #             isborder = True\n",
    "                    \n",
    "        #         else:\n",
    "        #             if not a[nx][ny]:\n",
    "        #                 a[nx][ny]=True\n",
    "        #                 dfs(nx,ny)\n",
    "        #     if isborder:\n",
    "        #         border.append([x,y])\n",
    "\n",
    "        # dfs(row,col)\n",
    "\n",
    "        # print(border)\n",
    "        # for x,y in border:\n",
    "        #     grid[x][y] = color\n",
    "        \n",
    "        # return grid\n",
    "\n",
    "        \n",
    "        m,n=len(grid),len(grid[0])\n",
    "        a = [[False]*n for _ in range(m)]\n",
    "\n",
    "        border = []\n",
    "        ori_color = grid[row][col]\n",
    "\n",
    "        a[row][col]=True\n",
    "        q = deque([[row,col]])\n",
    "        a[row][col]=True\n",
    "        dirs = [[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        \n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            isborder = False\n",
    "            \n",
    "            for dx,dy in dirs:\n",
    "                nx,ny = x+dx, y+dy\n",
    "                if not (0<=nx<m and 0<=ny<n and grid[nx][ny]==ori_color):\n",
    "                    isborder = True\n",
    "                elif not a[nx][ny]:\n",
    "                    a[nx][ny]=True\n",
    "                    q.append([nx,ny])\n",
    "            if isborder:\n",
    "                border.append([x,y])\n",
    "        \n",
    "\n",
    "        for x,y in border:\n",
    "            grid[x][y] = color\n",
    "        \n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(row, col)])\n",
    "        d = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        before = grid[row][col]\n",
    "        vis = set([(row, col)])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            cnt = 0\n",
    "            for i, j in d:\n",
    "                x1, y1 = x + i, y + j\n",
    "                if 0 <= x1 < m and 0 <= y1 < n:\n",
    "                    if grid[x1][y1] == before and (x1, y1) not in vis: \n",
    "                        vis.add((x1, y1))\n",
    "                        q.append((x1, y1))\n",
    "                    cnt += grid[x1][y1] == before or grid[x1][y1] == 0\n",
    "            if cnt < 4:\n",
    "                grid[x][y] = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    grid[i][j] = color\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs(grid, row, col, visited, borders, originalColor)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n",
    "    def dfs(self, grid, x, y, visited, borders, originalColor):  \n",
    "        isBorder = False        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        for dx, dy in direc:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                isBorder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid, nx, ny, visited, borders, originalColor)\n",
    "        if isBorder:\n",
    "            borders.append((x, y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        target=grid[row][col]\n",
    "        vis=set()\n",
    "        vis.add((row,col))\n",
    "        q=deque([(row,col)])\n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for x,y in (i+1,j),(i-1,j),(i,j-1),(i,j+1):\n",
    "                if (x,y) not in vis:\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y]==target:\n",
    "                        vis.add((x,y))\n",
    "                        q.append((x,y))\n",
    "                    else:\n",
    "                        grid[i][j]=color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        target=grid[row][col]\n",
    "        vis=set()\n",
    "        vis.add((row,col))\n",
    "        q=deque([(row,col)])\n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for x,y in (i+1,j),(i-1,j),(i,j-1),(i,j+1):\n",
    "                if (x,y) not in vis:\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y]==target:\n",
    "                        vis.add((x,y))\n",
    "                        q.append((x,y))\n",
    "                    else:\n",
    "                        grid[i][j]=color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if grid[i][j] == c:\n",
    "                    grid[i][j] = 0\n",
    "                    if dfs(i + 1, j) | dfs(i - 1, j) | dfs(i, j + 1) | dfs(i, j - 1):\n",
    "                        board.append((i, j))\n",
    "                    grid[i][j] = c\n",
    "                    return False\n",
    "                return grid[i][j] != 0\n",
    "            return True\n",
    "\n",
    "\n",
    "        m, n, c, board = len(grid), len(grid[0]), grid[row][col], []\n",
    "        dfs(row, col)\n",
    "        for i, j in board:\n",
    "            grid[i][j] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "        \n",
    "        oc = grid[row][col]\n",
    "        vis = [[0] * m for _ in range(n)]\n",
    "        def check(a, b, c, oc):\n",
    "            if a == 0 or a == n - 1 or b == 0 or b == m - 1:\n",
    "                # 处于grid边界一定为边界\n",
    "                grid[a][b] = c\n",
    "            elif not vis[a - 1][b] and grid[a - 1][b] != oc:\n",
    "                grid[a][b] = c\n",
    "            elif not vis[a + 1][b] and grid[a + 1][b] != oc:\n",
    "                grid[a][b] = c\n",
    "            elif not vis[a][b - 1] and grid[a][b - 1] != oc:\n",
    "                grid[a][b] = c\n",
    "            elif not vis[a][b + 1] and grid[a][b + 1] != oc:\n",
    "                grid[a][b] = c\n",
    "            \n",
    "\n",
    "\n",
    "        def bfs(i, j, c):\n",
    "            # 对该联通分量的边界进行染色\n",
    "            q = deque()\n",
    "            q.append([i, j])\n",
    "            vis[i][j] = 1\n",
    "            while len(q):\n",
    "                x, y = q.popleft()\n",
    "                check(x, y, c, oc)\n",
    "                for k in range(4):\n",
    "                    a = x + dx[k]\n",
    "                    b = y + dy[k]\n",
    "                    if a >= 0 and a < n and b >= 0 and b < m and vis[a][b] == 0 and grid[a][b] == oc:\n",
    "                        q.append([a, b])\n",
    "                        vis[a][b] = 1\n",
    "                        # check(a, b, c, oc)\n",
    "        bfs(row, col, color)\n",
    "        return grid\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        originalColor = grid[row][col]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        q = deque([(row, col)])\n",
    "        visited[row][col] = True\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            isBorder = False\n",
    "            for dx, dy in direc:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                    isBorder = True\n",
    "                elif not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    q.append((nx, ny))\n",
    "            if isBorder:\n",
    "                borders.append((x, y))\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        \"\"\"BFS实现边框着色\"\"\"\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        value = grid[row][col]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        queue = collections.deque()\n",
    "        queue.appendleft((row, col))\n",
    "        broder = []\n",
    "        visited[row][col] = 1\n",
    "        while queue:\n",
    "            i, j = queue.pop()\n",
    "            isBorder = False\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                # 通过当前节点四周的节点，判断当前节点是否是边界\n",
    "                if not (0<=x<m and 0<=y<n and grid[x][y] == value):\n",
    "                    isBorder = True\n",
    "                # 把四周符合的节点放进队列，等后面判断它是不是边界\n",
    "                elif visited[x][y] == 0:\n",
    "                    queue.appendleft((x, y))\n",
    "                    visited[x][y] = 1\n",
    "            if isBorder:\n",
    "                broder.append((i, j))\n",
    "        for i, j in broder:\n",
    "            grid[i][j] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class uniontree:\n",
    "    def __init__(self,m:int,n:int):\n",
    "        self.dict1={}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tuple1=(i,j)\n",
    "                self.dict1[tuple1]=tuple1\n",
    "    def find(self,x):\n",
    "        root=x\n",
    "        while root!=self.dict1[root]:\n",
    "            root=self.dict1[root]\n",
    "        while root!=x:\n",
    "            original_root=self.dict1[x]\n",
    "            self.dict1[x]=root\n",
    "            x=original_root\n",
    "        return root\n",
    "    def isconnected(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "    def union(self,x,y):\n",
    "        root_x,root_y=self.find(x),self.find(y)\n",
    "        if root_x!=root_y:\n",
    "            self.dict1[root_y]=root_x\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int):\n",
    "        # 可以采用并查集来做，也可以采用广度搜素的方法\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        tree1=uniontree(m,n)\n",
    "        next_=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for nx,ny in next_:\n",
    "                    nx_,ny_=nx+i,ny+j\n",
    "                    if 0<=nx_<m and 0<=ny_<n and grid[nx_][ny_]==grid[i][j]:\n",
    "                        tree1.union((i,j),(nx_,ny_))\n",
    "        dict1=defaultdict(list)\n",
    "        for key in tree1.dict1:\n",
    "            root=tree1.find(key)\n",
    "            dict1[root].append(key)\n",
    "        print(dict1)\n",
    "        isTrue=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                isTrue[i][j]=grid[i][j]\n",
    "        target_root=tree1.find((row,col))\n",
    "        list_=dict1[target_root]\n",
    "        print(target_root,list_)\n",
    "        for i,j in list_:\n",
    "            if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "                isTrue[i][j]=color\n",
    "                continue\n",
    "            for nx,ny in next_:\n",
    "                nx_,ny_=nx+i,ny+j\n",
    "                if 0<=nx_<m and 0<=ny_<n and grid[i][j]!=grid[nx_][ny_]:\n",
    "                    isTrue[i][j]=color\n",
    "        # for key in dict1:\n",
    "        #     root_list=dict1[key]\n",
    "        #     for i,j in root_list:\n",
    "        #         if i==0 or i==m-1 or j==0 or j==n-1:\n",
    "        #             isTrue[i][j]=color\n",
    "        #             continue\n",
    "        #         for nx,ny in next_:\n",
    "        #             nx_,ny_=i+nx,j+ny\n",
    "        #             if 0<=nx_<m and 0<=ny_<n and grid[i][j]!=grid[nx_][ny_]:\n",
    "        #                 isTrue[i][j]=color\n",
    "        return isTrue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs(grid, row, col, visited, borders, originalColor)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "    \n",
    "    def dfs(self, grid, x, y, visited, borders, originalColor):\n",
    "        isBorder = False\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        for dx, dy in direc:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                isBorder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid, nx, ny, visited, borders, originalColor)\n",
    "        if isBorder:\n",
    "            borders.append((x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid, row, col, color):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        que = collections.deque()\n",
    "        que.append((row,col))\n",
    "        originalColor = grid[row][col]\n",
    "        borders = []\n",
    "        vis = set()\n",
    "        \n",
    "        while que:\n",
    "            isBorder = False\n",
    "            v,u = que.popleft()\n",
    "            for i, j in [(v-1,u), (v+1,u), (v,u+1), (v,u-1)]:\n",
    "                if not (0<=i<m and 0<=j<n and grid[i][j]==originalColor):                \n",
    "                    isBorder = True\n",
    "                elif (i,j) not in vis:\n",
    "                    vis.add((i,j))\n",
    "                    que.append((i,j))\n",
    "            if isBorder: \n",
    "                borders.append((v,u))\n",
    "            \n",
    "\n",
    "        for x,y in borders:\n",
    "            grid[x][y] = color\n",
    "\n",
    "        return grid \n",
    "                    \n",
    "    \n",
    "\n",
    "                    \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 广搜，储存2个集合，一个是所有搜索过的地方，一个是不涂色的地方（非边界，中心）\n",
    "        source = grid[row][col]\n",
    "        seen = {(row, col)}\n",
    "        center = set()\n",
    "        q = deque([(row, col)])\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for r2, c2 in (r+1, c), (r-1, c), (r, c+1), (r, c-1):\n",
    "                if -1 < r2 < m and -1 < c2 < n:\n",
    "                    # 目标颜色\n",
    "                    if grid[r2][c2] == source:\n",
    "                        # 没见过\n",
    "                        if (r2, c2) not in seen:\n",
    "                            q.append((r2, c2))\n",
    "                            seen.add((r2, c2))\n",
    "                        # 见过，并且不知道是不是中心，那就检查这一块的四周是否都在见过中\n",
    "                        elif (r2, c2) not in center:\n",
    "                            if all((r3, c3) in seen for r3, c3 in ((r2+1, c2), (r2-1, c2), (r2, c2+1), (r2, c2-1))):\n",
    "                                # 如果四周都是目标颜色，不加入边界，加入中心\n",
    "                                center.add((r2, c2))\n",
    "\n",
    "        border = seen - center\n",
    "        for r, c in border:\n",
    "            grid[r][c] = color\n",
    "        return grid\n",
    "                            \n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        borders =[]\n",
    "        orcolor = grid[row][col]\n",
    "        visited[row][col]=True\n",
    "        self.dfs(grid,row,col,visited,borders,orcolor)\n",
    "        for x,y in borders:\n",
    "            grid[x][y] =color\n",
    "        return grid\n",
    "    \n",
    "    def dfs(self,grid,x,y,visited,borders,orcolor):\n",
    "        isborder = False\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        direc = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        for dx,dy in direc:\n",
    "            nx,ny = x+dx,y+dy\n",
    "            if not (0<=nx < m and 0<=ny<n and grid[nx][ny] == orcolor):\n",
    "                isborder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid,nx,ny,visited,borders,orcolor)\n",
    "        if isborder:\n",
    "            borders.append((x,y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 广搜，储存2个集合，一个是所有搜索过的地方，一个是不涂色的地方（非边界，中心）\n",
    "        source = grid[row][col]\n",
    "        seen = {(row, col)}\n",
    "        center = set()\n",
    "        q = deque([(row, col)])\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for r2, c2 in (r+1, c), (r-1, c), (r, c+1), (r, c-1):\n",
    "                if -1 < r2 < m and -1 < c2 < n:\n",
    "                    # 目标颜色\n",
    "                    if grid[r2][c2] == source:\n",
    "                        # 没见过\n",
    "                        if (r2, c2) not in seen:\n",
    "                            q.append((r2, c2))\n",
    "                            seen.add((r2, c2))\n",
    "                        # 见过，并且不知道是不是中心，那就检查这一块的四周是否都在见过中\n",
    "                        elif (r2, c2) not in center:\n",
    "                            if all((r3, c3) in seen for r3, c3 in ((r2+1, c2), (r2-1, c2), (r2, c2+1), (r2, c2-1))):\n",
    "                                # 如果四周都是目标颜色，不加入边界，加入中心\n",
    "                                center.add((r2, c2))\n",
    "\n",
    "        border = seen - center\n",
    "        for r, c in border:\n",
    "            grid[r][c] = color\n",
    "        return grid\n",
    "                            \n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        target = grid[row][col]\n",
    "        vis = set()\n",
    "        vis.add((row, col))\n",
    "        q = collections.deque([(row, col)])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1):\n",
    "                if (x, y) not in vis:\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] == target:\n",
    "                        vis.add((x, y))\n",
    "                        q.append((x, y))\n",
    "                    else:\n",
    "                        grid[i][j] = color\n",
    "        return grid "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs(grid, row, col, visited, borders, originalColor)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n",
    "    def dfs(self, grid, x, y, visited, borders, originalColor):  \n",
    "        isBorder = False        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        for dx, dy in direc:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                isBorder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid, nx, ny, visited, borders, originalColor)\n",
    "        if isBorder:\n",
    "            borders.append((x, y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        originalColor = grid[row][col]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        q = deque([(row, col)])\n",
    "        visited[row][col] = True\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            isBorder = False\n",
    "            for dx, dy in direc:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                    isBorder = True\n",
    "                elif not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    q.append((nx, ny))\n",
    "            if isBorder:\n",
    "                borders.append((x, y))\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])  # 行，列长度\n",
    "        visited = [[False] * n for _ in range(m)]  # 标记函数，记录是否访问过，节约内存\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs_stack(grid, row, col, visited, borders, originalColor)\n",
    "        for i, j in borders:\n",
    "            grid[i][j] = color#对边界染色\n",
    "        return grid\n",
    "\n",
    "    def dfs_stack(self, grid, row, col, visited, borders, originalColor):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        stack = [(row, col)]\n",
    "        while stack:\n",
    "            i, j = stack.pop()#栈不为空时取出栈顶元素\n",
    "            isBorder = False\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:#左右上下深度搜索\n",
    "                ni, nj = i + di, j + dj\n",
    "                if not (0 <= ni < m and 0 <= nj < n) or grid[ni][nj] != originalColor:#边界点为越界或者颜色与初始颜色不同的点\n",
    "                    isBorder = True\n",
    "                elif not visited[ni][nj]:\n",
    "                    visited[ni][nj] = True\n",
    "                    stack.append((ni, nj))#加入栈，以便下次搜索\n",
    "            if isBorder:\n",
    "                borders.append((i, j))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        queue = collections.deque([(row, col)])\n",
    "        seen = set([(row, col)])\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "\n",
    "            for di, dj in[(1,0), (-1,0),(0,1),(0,-1)]:\n",
    "                newi, newj = i + di, j + dj\n",
    "\n",
    "                if 0<=newi<r and 0<=newj<c and (newi, newj) not in seen and grid[newi][newj] == grid[row][col]:\n",
    "                    queue.append((newi, newj))\n",
    "                    seen.add((newi, newj))\n",
    "        \n",
    "        for (i, j) in seen:\n",
    "            if (i == 0 or i == r - 1) or (j == 0 or j == c - 1):\n",
    "                grid[i][j] = color\n",
    "                continue\n",
    "\n",
    "            if any((i + di, j + dj) not in seen for di, dj in [(1,0), (-1,0),(0,1),(0,-1)]):\n",
    "                grid[i][j] = color\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(row, col)])\n",
    "        d = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        before = grid[row][col]\n",
    "        vis = set([(row, col)])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            cnt = 0\n",
    "            for i, j in d:\n",
    "                x1, y1 = x + i, y + j\n",
    "                if 0 <= x1 < m and 0 <= y1 < n:\n",
    "                    if grid[x1][y1] == before and (x1, y1) not in vis: \n",
    "                        vis.add((x1, y1))\n",
    "                        q.append((x1, y1))\n",
    "                    cnt += grid[x1][y1] == before or grid[x1][y1] == 0\n",
    "            if cnt < 4:\n",
    "                grid[x][y] = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    grid[i][j] = color\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        originalColor = grid[row][col]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        q = deque([(row, col)])\n",
    "        visited[row][col] = True\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            isBorder = False\n",
    "            for dx, dy in direc:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                    isBorder = True\n",
    "                elif not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    q.append((nx, ny))\n",
    "            if isBorder:\n",
    "                borders.append((x, y))\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n",
    "                            \n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        '''\n",
    "        # 方法一：深度优先搜索\n",
    "        def dfs(i, j):\n",
    "            original_color = grid[i][j]\n",
    "            if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                grid[i][j] = color\n",
    "                visited.add((i, j))\n",
    "            for new_i, new_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:\n",
    "                    if grid[new_i][new_j] == original_color:\n",
    "                        visited.add((new_i, new_j))\n",
    "                        dfs(new_i, new_j)\n",
    "                    else:\n",
    "                        grid[i][j] = color\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set()\n",
    "        dfs(row, col)\n",
    "        return grid\n",
    "        '''\n",
    "\n",
    "        # 方法二：广度优先搜索\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set([(row, col)])\n",
    "        queue = [(row, col)]\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            original_color = grid[i][j]\n",
    "            if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                grid[i][j] = color\n",
    "            for new_i, new_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:\n",
    "                    if grid[new_i][new_j] == original_color:\n",
    "                        queue.append((new_i, new_j))\n",
    "                        visited.add((new_i, new_j))\n",
    "                    else:\n",
    "                        grid[i][j] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        self.grid = grid\n",
    "        self.c = color\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "        self.ans = [[0] * self.n for _ in range(self.m)]\n",
    "        self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        \n",
    "        self.dfs(row, col)\n",
    "        \n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if self.ans[i][j] == 0:\n",
    "                    self.ans[i][j] = grid[i][j]\n",
    "        \n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, x: int, y: int) -> None:\n",
    "        cnt = 0\n",
    "        for di in self.dirs:\n",
    "            nx = x + di[0]\n",
    "            ny = y + di[1]\n",
    "            \n",
    "            if nx < 0 or nx >= self.m or ny < 0 or ny >= self.n:\n",
    "                continue\n",
    "            \n",
    "            if self.grid[x][y] != self.grid[nx][ny]:\n",
    "                continue\n",
    "            \n",
    "            cnt += 1\n",
    "            if self.ans[nx][ny] != 0:\n",
    "                continue\n",
    "            \n",
    "            self.ans[nx][ny] = -1\n",
    "            self.dfs(nx, ny)\n",
    "        \n",
    "        self.ans[x][y] = self.grid[x][y] if cnt == 4 else self.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        # 获取原始颜色\n",
    "        originalColor = grid[row][col]\n",
    "\n",
    "        # 如果原始颜色与指定颜色相同，则不需要进行着色\n",
    "        if originalColor == color:\n",
    "            return grid\n",
    "\n",
    "        # 使用DFS函数对连通分量的边界进行着色\n",
    "        self.dfs(grid, row, col, originalColor, color, set())\n",
    "\n",
    "        return grid\n",
    "\n",
    "    def dfs(self, grid: List[List[int]], row: int, col: int, originalColor: int, newColor: int, visited: set) -> None:\n",
    "        # 检查是否已经访问过该方块\n",
    "        if (row, col) in visited:\n",
    "            return\n",
    "\n",
    "        # 检查当前方块是否与周围方块相邻\n",
    "        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != originalColor:\n",
    "            return\n",
    "\n",
    "        # 将当前方块加入已访问集合\n",
    "        visited.add((row, col))\n",
    "\n",
    "        # 继续搜索上、下、左、右四个相邻方块\n",
    "        self.dfs(grid, row-1, col, originalColor, newColor, visited)\n",
    "        self.dfs(grid, row+1, col, originalColor, newColor, visited)\n",
    "        self.dfs(grid, row, col-1, originalColor, newColor, visited)\n",
    "        self.dfs(grid, row, col+1, originalColor, newColor, visited)\n",
    "\n",
    "        # 检查当前方块是否在边界上或与不属于同一连通分量的方块相邻\n",
    "        if row == 0 or row == len(grid)-1 or col == 0 or col == len(grid[0])-1 \\\n",
    "                or (row-1, col) not in visited or (row+1, col) not in visited \\\n",
    "                or (row, col-1) not in visited or (row, col+1) not in visited:\n",
    "            grid[row][col] = newColor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs(grid, row, col, visited, borders, originalColor)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n",
    "    def dfs(self, grid, x, y, visited, borders, originalColor):  \n",
    "        isBorder = False        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        for dx, dy in direc:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                isBorder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid, nx, ny, visited, borders, originalColor)\n",
    "        if isBorder:\n",
    "            borders.append((x, y))\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (-1 ,0), (1, 0)]\n",
    "\n",
    "        def is_board(grid: list[list[int]], i: int, j: int, visited: list[list[bool]], new_color: int) -> bool:\n",
    "            if i - 1 < 0 or j - 1 < 0 or i + 1 >= m or j + 1 >= n:\n",
    "                return True\n",
    "            color = grid[i][j]\n",
    "            for dx, dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy\n",
    "                # 任意一个格子没被访问的，且颜色不同的，则认为是边界\n",
    "                if (not visited[nxt_i][nxt_j] and grid[nxt_i][nxt_j] != color):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(grid: list[list[int]], i: int, j: int, old_color: int, new_color: int, visited: list[list[bool]]) -> None:\n",
    "            if is_board(grid, i, j, visited, new_color):\n",
    "                # 边界着色\n",
    "                grid[i][j] = new_color\n",
    "\n",
    "            visited[i][j] = True\n",
    "            \n",
    "            for dx,dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy \n",
    "                if 0 <= nxt_i < m and 0 <= nxt_j < n and grid[nxt_i][nxt_j] == old_color and not visited[nxt_i][nxt_j]:\n",
    "                    dfs(grid, nxt_i, nxt_j, old_color, new_color, visited)\n",
    "        \n",
    "        dfs(grid, row, col, grid[row][col], color, visited)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        explorted = set()\n",
    "\n",
    "        def DFS(r,c):\n",
    "            if r<0 or c<0 or r == m or c == n:\n",
    "                return True\n",
    "            if (r,c) in explorted:\n",
    "                return False\n",
    "            if grid[r][c] != grid[row][col]:\n",
    "                return True\n",
    "            explorted.add((r,c))\n",
    "            ans = False\n",
    "            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):\n",
    "                if DFS(r+dx,c+dy):\n",
    "                    ans = True\n",
    "            if ans:\n",
    "                grid[r][c] = color\n",
    "            return False\n",
    "        DFS(row,col)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        originalColor = grid[row][col]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        q = deque([(row, col)])\n",
    "        visited[row][col] = True\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            isBorder = False\n",
    "            for dx, dy in direc:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                    isBorder = True\n",
    "                elif not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    q.append((nx, ny))\n",
    "            if isBorder:\n",
    "                borders.append((x, y))\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.bfs_queue(grid, row, col, visited, borders, originalColor)\n",
    "        for i, j in borders:\n",
    "            grid[i][j] = color\n",
    "        return grid\n",
    "\n",
    "    def bfs_queue(self, grid, row, col, visited, borders, originalColor):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direc = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        queue = deque([(row, col)])\n",
    "        \n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "            isBorder = False\n",
    "\n",
    "            for di, dj in direc:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if not (0 <= ni < m and 0 <= nj < n) or grid[ni][nj] != originalColor:\n",
    "                    isBorder = True\n",
    "                elif not visited[ni][nj]:\n",
    "                    visited[ni][nj] = True\n",
    "                    queue.append((ni, nj))\n",
    "\n",
    "            if isBorder:\n",
    "                borders.append((i, j))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        draw=[[0]*len(grid[0]) for _ in grid]\n",
    "        \n",
    "        q=queue.deque([(row,col)])\n",
    "        seen=set((row,col))\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                y,x=q.popleft()\n",
    "                if y==0 or y==len(grid)-1 or x==0 or x==len(grid[0])-1:\n",
    "                    draw[y][x]=1\n",
    "                for by,bx in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                    ty,tx=y+by,x+bx\n",
    "                    if 0<=ty<len(grid) and 0<=tx<len(grid[0]):\n",
    "                        if (ty,tx) not in seen and grid[ty][tx]==grid[y][x]:\n",
    "                            seen.add((ty,tx))\n",
    "                            q.append((ty,tx))\n",
    "                        if grid[ty][tx]!=grid[y][x]:\n",
    "                            draw[y][x] = 1\n",
    "        for y in range(len(grid)):\n",
    "            for x in range(len(grid[0])):\n",
    "                if draw[y][x]==1:\n",
    "                    grid[y][x]=color\n",
    "        return grid\n",
    "    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set((row, col))\n",
    "        queue = [(row, col)]\n",
    "        boarder = []\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            original_color = grid[i][j]\n",
    "            isboarder = False\n",
    "            if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                isboarder = True\n",
    "            for new_i, new_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:\n",
    "                    if grid[new_i][new_j] == original_color:\n",
    "                        queue.append((new_i, new_j))\n",
    "                        visited.add((new_i, new_j))\n",
    "                    else:\n",
    "                        isboarder = True\n",
    "            if isboarder:\n",
    "                boarder.append((i, j))\n",
    "        for x, y  in boarder:\n",
    "            grid[x][y] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        liantong = []\n",
    "\n",
    "        def DFS(x, y):\n",
    "            if x < 0 or y < 0 or x >= rows or y >= cols:\n",
    "                return\n",
    "            if grid[x][y] != grid[row][col]:\n",
    "                return\n",
    "            if (x, y) in liantong:\n",
    "                return\n",
    "            liantong.append((x, y))\n",
    "            for m, n in directions:\n",
    "                new_x, new_y = x + m, y + n\n",
    "                DFS(new_x, new_y)\n",
    "        \n",
    "        DFS(row, col)\n",
    "        \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if (i, j) in liantong:\n",
    "                    if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:\n",
    "                        grid[i][j] = color\n",
    "                    elif any((i + m, j + n) not in liantong for m, n in directions):\n",
    "                        grid[i][j] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        q = [(row, col)]\n",
    "        originColor = grid[row][col]\n",
    "        if color == grid[row][col]: return grid\n",
    "        def changeIfNeed(i, j):\n",
    "            if grid[i][j] < 0: return\n",
    "            if i<=0 or j<=0 or i>=len(grid)-1 or j>=len(grid[0])-1:\n",
    "                grid[i][j] = -grid[i][j]\n",
    "                return\n",
    "            \n",
    "            if any([abs(grid[i+x][j+y]) != grid[i][j] for x, y in ((-1, 0), (1, 0), (0, 1), (0, -1))]):\n",
    "                grid[i][j] = -grid[i][j]\n",
    "        visited = set([(row, col)])\n",
    "        while q:\n",
    "            i, j = q.pop(0)\n",
    "            changeIfNeed(i, j)\n",
    "            \n",
    "            for x, y in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                ni, nj = i+x, j+y\n",
    "                if ni<0 or nj<0 or ni>len(grid)-1 or nj>len(grid[0])-1 or grid[ni][nj] != originColor or (ni, nj) in visited:\n",
    "                    continue\n",
    "                q.append((ni, nj))\n",
    "                visited.add((ni, nj))\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] < 0:\n",
    "                    grid[i][j] = color\n",
    "        return grid\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        basic_color = grid[row][col]\n",
    "        dir = ((1, 0), (0, 1), (-1, 0), (0, -1))\n",
    "        vis = [(row, col)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for a, b in dir:\n",
    "                nx, ny = x + a, y + b\n",
    "                # if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] != basic_color and (nx, ny) not in vis:\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == basic_color and (nx, ny) not in vis:\n",
    "                    vis.append((nx, ny))\n",
    "                    dfs(nx, ny)\n",
    "                else:\n",
    "                    if (nx, ny) not in vis:\n",
    "                        grid[x][y] = color\n",
    "\n",
    "        dfs(row, col)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        ans=set()\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vis=[[0]*n for _ in range(m)]\n",
    "        raw=grid[row][col]\n",
    "        if row==0 or row==m-1 or col==0 or col==n-1:\n",
    "            ans.add((row,col))\n",
    "        queue=deque([[row,col]])\n",
    "        vis[row][col]=1\n",
    "        dic=[[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        while queue:\n",
    "            a,b=queue.popleft()\n",
    "            flag=0\n",
    "            for x,y in dic:\n",
    "                x+=a\n",
    "                y+=b\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if grid[x][y]!=raw:\n",
    "                        flag=1\n",
    "                    elif vis[x][y]==0:\n",
    "                        queue.append([x,y])\n",
    "                        vis[x][y]=1\n",
    "                        if x==0 or x==m-1 or y==0 or y==n-1:\n",
    "                            ans.add((x,y))\n",
    "                if flag==1:\n",
    "                    ans.add((a,b))\n",
    "        for i,j in ans:\n",
    "            grid[i][j]=color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        #四个方向\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        def DFS(x, y):\n",
    "            if x < 0 or x >= rows or y < 0 or y >= cols:\n",
    "                return\n",
    "            if grid[x][y] != grid[row][col]:\n",
    "                return\n",
    "            if (x, y) in visited:\n",
    "                return\n",
    "            visited.add((x, y))\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                DFS(new_x, new_y)\n",
    "        \n",
    "        visited = set()\n",
    "        DFS(row, col)\n",
    "        \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if (i, j) in visited:\n",
    "                    if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:\n",
    "                        grid[i][j] = color\n",
    "                    elif any((i + dx, j + dy) not in visited for dx, dy in directions):\n",
    "                        grid[i][j] = color\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ggrid = []\n",
    "        for i in range(m):\n",
    "            ggrid.append([])\n",
    "            for j in range(n):\n",
    "                ggrid[i].append(grid[i][j])\n",
    "\n",
    "        q= deque()\n",
    "        node ={}\n",
    "        q.append([row,col])\n",
    "        node[(row,col)] = True\n",
    "        colors = grid[row][col]\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            time = 0\n",
    "            for (xi,yi) in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                xx = x+xi\n",
    "                yy = y+yi\n",
    "                if xx<m and xx>=0 and yy<n and yy>=0 and ggrid[xx][yy]==colors: \n",
    "                    if (xx,yy) not in node.keys():\n",
    "                        q.append([xx,yy])\n",
    "                        node[(xx,yy)] = True\n",
    "                    time+=1\n",
    "            if time < 4:\n",
    "                grid[x][y] = color\n",
    "        return grid \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        borders = []\n",
    "        originalColor = grid[row][col]\n",
    "        visited[row][col] = True\n",
    "        self.dfs(grid, row, col, visited, borders, originalColor)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n",
    "    def dfs(self, grid, x, y, visited, borders, originalColor):  \n",
    "        isBorder = False        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        for dx, dy in direc:\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):\n",
    "                isBorder = True\n",
    "            elif not visited[nx][ny]:\n",
    "                visited[nx][ny] = True\n",
    "                self.dfs(grid, nx, ny, visited, borders, originalColor)\n",
    "        if isBorder:\n",
    "            borders.append((x, y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:\n",
    "        # 空值判断\n",
    "        if not grid:\n",
    "            return []\n",
    "        # 四个方向\n",
    "        pos = [(-1, 0), (1, 0), (0, -1), (0, 1)]  \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 访问标记\n",
    "        visited = set()\n",
    "        visited.add((r0,c0))\n",
    "        # 初始值\n",
    "        target=grid[r0][c0]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            # 遍历4个方向\n",
    "            for i,j in pos:\n",
    "                a=x+i\n",
    "                b=y+j\n",
    "\n",
    "                # 判断是否在网格范围内\n",
    "                if 0 <= a < m and 0 <= b < n:\n",
    "                    # 判断是否访问过\n",
    "                    if (a,b) not in visited:\n",
    "                        # 如果下一个位置颜色与当前颜色相同，则继续搜索，并将下一个位置标记为已访问\n",
    "                        if grid[a][b] == target:\n",
    "                            visited.add((a,b))\n",
    "                            dfs(a,b)\n",
    "                        else:\n",
    "                            # # 下个位置颜色和当前颜色不同，说明当前位置是连通区域边界，着色\n",
    "                            grid[x][y] = color\n",
    "                else:\n",
    "                    # 下一个点越界，说明当前点在网格边界上，着色\n",
    "                    grid[x][y] = color\n",
    "\n",
    "        dfs(r0, c0) \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        @cache\n",
    "        def isInGrid(x,y):\n",
    "            if x>=0 and x<=n-1:\n",
    "                if y>=0 and y<=m-1:\n",
    "                    return True\n",
    "            return False\n",
    "        ward = [[-1,0],[0,-1],[0,1],[1,0]]\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        arr = [[row,col]]\n",
    "        init = grid[row][col]\n",
    "        table = {}\n",
    "        ans = []\n",
    "        while arr:\n",
    "            #print(arr)\n",
    "            temp = []\n",
    "            while arr:\n",
    "                x,y = arr.pop()\n",
    "                if x*m+y in table:\n",
    "                    continue\n",
    "                table[x*m+y] = 1\n",
    "                \n",
    "                for a,b in ward:\n",
    "                    j = a + x\n",
    "                    k = b + y\n",
    "                    if isInGrid(j,k):\n",
    "                        if grid[j][k]!= init:\n",
    "                            ans.append([x,y])\n",
    "                            #grid[x][y] = color\n",
    "                        else:\n",
    "                            temp.append([j,k])\n",
    "                    else:\n",
    "                        #grid[x][y] = color\n",
    "                        ans.append([x,y])\n",
    "            arr = temp.copy()\n",
    "        for x,y in ans:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (-1 ,0), (1, 0)]\n",
    "\n",
    "        def is_board(grid: list[list[int]], i: int, j: int, visited: list[list[bool]], new_color: int) -> bool:\n",
    "            if i - 1 < 0 or j - 1 < 0 or i + 1 >= m or j + 1 >= n:\n",
    "                return True\n",
    "            color = grid[i][j]\n",
    "            # if grid[i - 1][j] == color and grid[i + 1][j] == color and grid[i][j - 1] == color and grid[i][j + 1] == color:\n",
    "            #     return False\n",
    "            for dx, dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy\n",
    "                if (not visited[nxt_i][nxt_j] and grid[nxt_i][nxt_j] != color):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(grid: list[list[int]], i: int, j: int, old_color: int, new_color: int, visited: list[list[bool]]) -> None:\n",
    "            if i == 2 and j == 1:\n",
    "                print(is_board(grid, i, j, visited, new_color), visited)\n",
    "            if is_board(grid, i, j, visited, new_color):\n",
    "                \n",
    "                grid[i][j] = new_color\n",
    "\n",
    "            visited[i][j] = True\n",
    "            \n",
    "            for dx,dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy \n",
    "                if 0 <= nxt_i < m and 0 <= nxt_j < n and grid[nxt_i][nxt_j] == old_color and not visited[nxt_i][nxt_j]:\n",
    "                    dfs(grid, nxt_i, nxt_j, old_color, new_color, visited)\n",
    "        \n",
    "        dfs(grid, row, col, grid[row][col], color, visited)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = [(row, col)]\n",
    "        visited = set(q)\n",
    "        board = copy.deepcopy(grid)\n",
    "        while q:\n",
    "            x, y = q.pop(0)\n",
    "            if x == 0 or x == m - 1 or y == 0 or y == n - 1:\n",
    "                board[x][y] = color\n",
    "            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or (nx, ny) in visited:\n",
    "                    continue\n",
    "                if grid[nx][ny] == grid[x][y]:\n",
    "                    visited.add((nx, ny))\n",
    "                    q.append((nx, ny))\n",
    "                else:\n",
    "                    board[x][y] = color\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def dfs(i,j):\n",
    "            #print(i,j)\n",
    "            con[i][j] = True\n",
    "            for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if (0 <= k1 < m and 0 <= k2 < n) and grid[k1][k2] == grid[i][j] and not con[k1][k2]:\n",
    "                    dfs(k1,k2)\n",
    "\n",
    "        def diff(i,j):\n",
    "            for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if (0 <= k1 < m and 0 <= k2 < n) and grid[k1][k2] != grid[i][j]:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        con = [[False]*n for _ in range(m)]\n",
    "        dfs(row,col)\n",
    "        #print(con)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not con[i][j]: continue \n",
    "                if i == 0 or i == m-1 or j == 0 or j == n-1: continue\n",
    "                #print(i,j,diff(i,j))\n",
    "                if not diff(i,j): \n",
    "                    con[i][j] = False\n",
    "                \n",
    "        #print(con)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if con[i][j]: \n",
    "                    grid[i][j] = color\n",
    "        return grid\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (-1 ,0), (1, 0)]\n",
    "\n",
    "        def is_board(grid: list[list[int]], i: int, j: int, visited: list[list[bool]], new_color: int) -> bool:\n",
    "            if i - 1 < 0 or j - 1 < 0 or i + 1 >= m or j + 1 >= n:\n",
    "                return True\n",
    "            color = grid[i][j]\n",
    "            for dx, dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy\n",
    "                if (not visited[nxt_i][nxt_j] and grid[nxt_i][nxt_j] != color):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(grid: list[list[int]], i: int, j: int, old_color: int, new_color: int, visited: list[list[bool]]) -> None:\n",
    "\n",
    "            if is_board(grid, i, j, visited, new_color):\n",
    "                grid[i][j] = new_color\n",
    "\n",
    "            visited[i][j] = True\n",
    "            \n",
    "            for dx,dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy \n",
    "                if 0 <= nxt_i < m and 0 <= nxt_j < n and grid[nxt_i][nxt_j] == old_color and not visited[nxt_i][nxt_j]:\n",
    "                    dfs(grid, nxt_i, nxt_j, old_color, new_color, visited)\n",
    "        \n",
    "        dfs(grid, row, col, grid[row][col], color, visited)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (-1 ,0), (1, 0)]\n",
    "\n",
    "        def is_board(grid: list[list[int]], i: int, j: int, visited: list[list[bool]], new_color: int) -> bool:\n",
    "            if i - 1 < 0 or j - 1 < 0 or i + 1 >= m or j + 1 >= n:\n",
    "                return True\n",
    "            color = grid[i][j]\n",
    "            for dx, dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy\n",
    "                if (not visited[nxt_i][nxt_j] and grid[nxt_i][nxt_j] != color):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(grid: list[list[int]], i: int, j: int, old_color: int, new_color: int, visited: list[list[bool]]) -> None:\n",
    "\n",
    "            if is_board(grid, i, j, visited, new_color):\n",
    "                \n",
    "                grid[i][j] = new_color\n",
    "\n",
    "            visited[i][j] = True\n",
    "            \n",
    "            for dx,dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy \n",
    "                if 0 <= nxt_i < m and 0 <= nxt_j < n and grid[nxt_i][nxt_j] == old_color and not visited[nxt_i][nxt_j]:\n",
    "                    dfs(grid, nxt_i, nxt_j, old_color, new_color, visited)\n",
    "        \n",
    "        dfs(grid, row, col, grid[row][col], color, visited)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        direcitons = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        original_color = grid[row][col]\n",
    "        visited = set()\n",
    "        border = set()\n",
    "        def isBorder(x, y):\n",
    "            if x == 0 or x == m - 1 or y == 0 or y == n - 1:\n",
    "                return True\n",
    "            for dx, dy in direcitons:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if grid[nx][ny] != original_color:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if (x, y) in visited or not (0 <= x < m and 0 <= y < n) or grid[x][y] != original_color:\n",
    "                return\n",
    "            if isBorder(x, y):\n",
    "                border.add((x, y))\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for dx, dy in direcitons:\n",
    "                dfs(x + dx, y + dy)\n",
    "\n",
    "        dfs(row, col)\n",
    "\n",
    "        for r, c in border:\n",
    "            grid[r][c] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)] #超出空间?\n",
    "        ori_color = grid[row][col]\n",
    "        re = []\n",
    "        def dfs(row,col):\n",
    "            #判断是否边界，染色\n",
    "            visited[row][col] = 1\n",
    "            if row == 0 or row == m-1 or col == 0 or col == n-1:\n",
    "                re.append((row,col))\n",
    "            elif grid[row-1][col] != ori_color or grid[row+1][col] != ori_color or grid[row][col-1] != ori_color or grid[row][col+1] != ori_color:\n",
    "                re.append((row,col))\n",
    "            temp = []\n",
    "            #添加未访问同种颜色相邻块\n",
    "            if row != 0 and grid[row-1][col] == ori_color and visited[row-1][col] == 0:\n",
    "                temp.append((row-1,col))\n",
    "            if row != m-1 and grid[row+1][col] == ori_color and visited[row+1][col] == 0:\n",
    "                temp.append((row+1,col))\n",
    "            if col != 0 and grid[row][col-1] == ori_color and visited[row][col-1] == 0:\n",
    "                temp.append((row,col-1))\n",
    "            if col != n-1 and grid[row][col+1] == ori_color and visited[row][col+1] == 0:\n",
    "                temp.append((row,col+1)) \n",
    "            for ma in temp:\n",
    "                dfs(*ma) \n",
    "        dfs(row,col)\n",
    "        for row,col in re:\n",
    "            grid[row][col] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        explored = set() #设置一个集合保存已经遍历过的点\n",
    "\n",
    "        def dfs(r, c):\n",
    "            if r < 0 or c < 0 or r == m or c == n:  #如果点在0外或者区域外返回true，改变ans的标记\n",
    "                return True\n",
    "            if (r,c) in explored:   #如果该点已经遍历返回false，表示continue，不改变ans的标记\n",
    "                return False\n",
    "            if grid[r][c] != grid[row][col]:  #如果该点是连通分量，也返回TRUE\n",
    "                return True\n",
    "            explored.add((r,c))   #把该点记入集合中\n",
    "            ans = False  #初始化ans标号\n",
    "            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):  #遍历上下左右四个点\n",
    "                if dfs(r+dx,c+dy):  #如果该点为边界或者四个点内有连通分量把ans标为true\n",
    "                    ans = True    \n",
    "            if ans:  #如果满足判定要求\n",
    "                grid[r][c] = color   #给该点染色\n",
    "            return False     #染完色后退出循环\n",
    "        \n",
    "        dfs(row, col)\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        d=[-1,1,0,0]\n",
    "        u=[0,0,-1,1]\n",
    "        vis=set()\n",
    "        hello=grid[row][col]\n",
    "        def bfss(x,y):\n",
    "            vis.add((x,y))\n",
    "            for k in range(4):\n",
    "                a=x+u[k]\n",
    "                b=y+d[k]\n",
    "                if (a,b) not in vis:\n",
    "                    if 0<=a<=m-1 and 0<=b<=n-1 and grid[a][b]==hello :\n",
    "                        bfss(a,b)\n",
    "                    else:\n",
    "                        grid[x][y]=color\n",
    "        bfss(row,col)\n",
    "        return grid\n",
    "               \n",
    "            \n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n = len(grid), len(grid[0]) \n",
    "        boarder = []\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        clk = 0 \n",
    "        def dfs(x, y):\n",
    "            nonlocal clk \n",
    "            clk += 1\n",
    "            vis[x][y] = 1\n",
    "            flag = 0\n",
    "            for [nx,ny] in [[x+1,y], [x-1,y], [x,y+1], [x,y-1]]:\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny] == grid[x][y]:\n",
    "                    if not vis[nx][ny]:\n",
    "                        dfs(nx,ny)\n",
    "                else:\n",
    "                    flag = 1\n",
    "            if flag:\n",
    "                boarder.append((x,y)) \n",
    "            vis[x][y] = 2\n",
    "            clk += 1\n",
    "        dfs(row, col) \n",
    "        for x, y in boarder:\n",
    "            grid[x][y] = color \n",
    "        return grid "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        c = grid[row][col]\n",
    "        visited ={(row,col)}\n",
    "        pos=[(-1,0),(0,-1),(1,0),(0,1)]\n",
    "        def dfs(x,y):\n",
    "            for i,j in pos:\n",
    "                a = x+i \n",
    "                b = y+j\n",
    "                if 0<=a<m and 0<=b<n:\n",
    "                    if (a,b) not in visited:\n",
    "                        if grid[a][b] == c:\n",
    "                            visited.add((a,b))\n",
    "                            dfs(a,b)\n",
    "                        else:#即周围有异色区域\n",
    "                            grid[x][y] = color \n",
    "                else:#说明该点是边界\n",
    "                    grid[x][y] = color \n",
    "        dfs(row,col)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        b = grid[row][col]\n",
    "\n",
    "\n",
    "        def dfs(r, c):\n",
    "            if r < 0 or c < 0 or r == m or c == n:\n",
    "                return True\n",
    "            if not grid[r][c] or grid[r][c] == -1:\n",
    "                return False\n",
    "            if grid[r][c] != b:\n",
    "                return True\n",
    "            grid[r][c], ans = 0, False\n",
    "            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):\n",
    "                if dfs(r+dx,c+dy):\n",
    "                    ans = True\n",
    "            if ans:\n",
    "                grid[r][c] = -1\n",
    "            return False\n",
    "        \n",
    "        dfs(row, col)\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if not grid[r][c]:\n",
    "                    grid[r][c] = b\n",
    "                elif grid[r][c] == -1:\n",
    "                    grid[r][c] = color\n",
    "        return grid\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        explorted = set()\n",
    "\n",
    "        def DFS(r,c):\n",
    "            if r<0 or c<0 or r == m or c == n:\n",
    "                return True\n",
    "            if (r,c) in explorted:\n",
    "                return False\n",
    "            if grid[r][c] != grid[row][col]:\n",
    "                return True\n",
    "            explorted.add((r,c))\n",
    "            ans = False\n",
    "            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):\n",
    "                if DFS(r+dx,c+dy):\n",
    "                    ans = True\n",
    "            if ans:\n",
    "                grid[r][c] = color\n",
    "            return False\n",
    "        DFS(row,col)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        d=[-1,1,0,0]\n",
    "        u=[0,0,-1,1]\n",
    "        vis=set()\n",
    "        hello=grid[row][col]\n",
    "        def bfss(x,y):\n",
    "            vis.add((x,y))\n",
    "            for k in range(4):\n",
    "                a=x+u[k]\n",
    "                b=y+d[k]\n",
    "                if (a,b) not in vis:\n",
    "                    if 0<=a<=m-1 and 0<=b<=n-1 and grid[a][b]==hello :\n",
    "                        bfss(a,b)\n",
    "                    else:\n",
    "                        grid[x][y]=color\n",
    "        bfss(row,col)\n",
    "        return grid\n",
    "               \n",
    "            \n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = []\n",
    "        ori_color = grid[row][col]\n",
    "        re = []\n",
    "        def dfs(row,col):\n",
    "            #判断是否边界，染色\n",
    "            visited.append((row,col))\n",
    "            if row == 0 or row == m-1 or col == 0 or col == n-1:\n",
    "                re.append((row,col))\n",
    "            elif grid[row-1][col] != ori_color or grid[row+1][col] != ori_color or grid[row][col-1] != ori_color or grid[row][col+1] != ori_color:\n",
    "                re.append((row,col))\n",
    "            temp = []\n",
    "            #添加未访问同种颜色相邻块\n",
    "            if row != 0 and grid[row-1][col] == ori_color and (row-1,col) not in visited:\n",
    "                temp.append((row-1,col))\n",
    "            if row != m-1 and grid[row+1][col] == ori_color and (row+1,col) not in visited:\n",
    "                temp.append((row+1,col))\n",
    "            if col != 0 and grid[row][col-1] == ori_color and (row,col-1) not in visited:\n",
    "                temp.append((row,col-1))\n",
    "            if col != n-1 and grid[row][col+1] == ori_color and (row,col+1) not in visited:\n",
    "                temp.append((row,col+1)) \n",
    "            for ma in temp:\n",
    "                dfs(*ma) \n",
    "        dfs(row,col)\n",
    "        for row,col in re:\n",
    "            grid[row][col] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        v=Counter([(row,col)])\n",
    "        c=grid[row][col]\n",
    "        def g(i,j):\n",
    "           for a,b in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "               x=i+a\n",
    "               y=j+b\n",
    "               if 0<=x<n and 0<=y<m and grid[x][y]==c and v[(x,y)]==0:\n",
    "                  v[(x,y)]+=1 \n",
    "                  g(x,y)\n",
    "        g(row,col)\n",
    "        print(v)          \n",
    "        for i in range(n):\n",
    "            for  j in range(m):\n",
    "               if (i,j) in v:\n",
    "                  print(1) \n",
    "                  for a,b in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                      x=i+a\n",
    "                      y=j+b\n",
    "                      if (x,y) not in v or x==-1 or x ==n or y==-1 or y==m:\n",
    "                         grid[i][j]=color\n",
    "        return grid                                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        # m, n = len(grid[0]), len(grid)\n",
    "        # visited = set()\n",
    "        # isborder = False\n",
    "\n",
    "        # def dfs(i, j, val):\n",
    "        #     if not 0<=i<n or not 0<=j<m or (i,j) in visited:\n",
    "        #         return \n",
    "        #     visited.add((i, j))\n",
    "        #     if grid[i][j] != val:\n",
    "        #         return\n",
    "        #     grid[i][j] = color\n",
    "        #     for ni, nj in ((i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j)):\n",
    "        #         dfs(ni, nj, val)\n",
    "        \n",
    "        # dfs(row, col, grid[row][col])\n",
    "        # return grid\n",
    "        def dfs(i: int, j: int, c: int) -> None:\n",
    "            vis[i][j] = True\n",
    "            for a, b in pairwise((-1, 0, 1, 0, -1)):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if not vis[x][y]:\n",
    "                        if grid[x][y] == c:\n",
    "                            dfs(x, y, c)\n",
    "                        else:\n",
    "                            grid[i][j] = color\n",
    "                else:\n",
    "                    grid[i][j] = color\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        dfs(row, col, grid[row][col])\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, G: List[List[int]], r: int, c: int, C: int) -> List[List[int]]:\n",
    "        X, book = G[r][c], set()\n",
    "        def dfs(r, c):\n",
    "            if (r, c) in book: return 1\n",
    "            if r in (-1, len(G)) or c in (-1, len(G[0])) or G[r][c] != X: return 0\n",
    "            else: book.add((r, c))\n",
    "            if sum(dfs(r + dr, c + dc) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))) != 4: G[r][c] = C\n",
    "            return 1\n",
    "        dfs(r, c)\n",
    "        return G\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        neighbor = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        oc = grid[row][col]\n",
    "        borders = []\n",
    "        def dfs(x,y,borders):\n",
    "            isboard = False\n",
    "            for dx, dy in neighbor:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if not(0<=nx<m and 0<=ny<n and grid[nx][ny] == oc):\n",
    "                    isboard = True\n",
    "                elif not visited[nx][ny]:\n",
    "                    visited[nx][ny] = True\n",
    "                    dfs(nx,ny,borders)\n",
    "            if isboard:\n",
    "                print(x,y)\n",
    "                borders.append((x,y))\n",
    "        \n",
    "        dfs(row,col,borders)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        # 方法一：深度优先搜索\n",
    "        def dfs(i, j):\n",
    "            original_color = grid[i][j]\n",
    "            if i == 0 or i == m-1 or j == 0 or j == n-1:\n",
    "                grid[i][j] = color\n",
    "                visited.add((i, j))\n",
    "            for new_i, new_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:\n",
    "                    if grid[new_i][new_j] == original_color:\n",
    "                        visited.add((new_i, new_j))\n",
    "                        dfs(new_i, new_j)\n",
    "                    else:\n",
    "                        grid[i][j] = color\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set()\n",
    "        dfs(row, col)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        '''\n",
    "        是给边界进行着色\n",
    "        '''\n",
    "        def dfs(i,j):\n",
    "            vis[i][j]=True\n",
    "            for u,v in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=u<m and 0<=v<n and grid[u][v]!=k or u==-1 or u==m or v==-1 or v==n:\n",
    "                        s.add((i,j))\n",
    "            for u,v in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=u<m and 0<=v<n and grid[u][v]==k and not vis[u][v]:\n",
    "                    dfs(u,v)\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k=grid[row][col]\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        s=set()\n",
    "        dfs(row,col)\n",
    "        for x,y in s:\n",
    "            grid[x][y]=color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        vis = set()\n",
    "        vis.add((row,col))\n",
    "        target = grid[row][col]\n",
    "\n",
    "        def dfs(x,y):\n",
    "            for i,j in [x-1,y],[x+1,y],[x,y-1],[x,y+1]:\n",
    "                if 0 <= i < m and 0 <= j < n:\n",
    "                    if (i,j) not in vis:\n",
    "                        if grid[i][j] == target:\n",
    "                            vis.add((i,j))\n",
    "                            dfs(i,j)\n",
    "                        else:\n",
    "                            grid[x][y] = color\n",
    "                else:\n",
    "                    grid[x][y] = color\n",
    "            \n",
    "        dfs(row,col)\n",
    "        return grid\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "\n",
    "        nowcolor = grid[row][col]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            visited[x][y] = 1\n",
    "            inout = False\n",
    "            \n",
    "            if x == 0 or y == 0 or x == m-1 or y == n-1:\n",
    "                inout = True\n",
    "\n",
    "            for i, j in ((x-1, y),(x+1, y),(x, y-1),(x, y+1)):\n",
    "                if 0 <= i < m and 0 <= j < n and not visited[i][j]:\n",
    "                    if grid[i][j] != nowcolor:\n",
    "                        inout = True   \n",
    "                    else:\n",
    "                        dfs(i,j)\n",
    "            if inout:\n",
    "                grid[x][y] =  color\n",
    "            \n",
    "            return\n",
    "        \n",
    "        dfs(row, col)\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS. Time O(mn) Space O(mn)\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        def dfs(x, y, original):\n",
    "            if vis[x][y]: return\n",
    "            vis[x][y] = True\n",
    "            isBorder = False\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == original:\n",
    "                    dfs(nx, ny, original)\n",
    "                else:\n",
    "                    isBorder = True\n",
    "            if isBorder: borders.append((x, y))\n",
    "        # Use vis instead of sinking island, as we need to keep them in res returned\n",
    "        vis = [[False for _ in range(n)] for _ in range(m)]\n",
    "        original = grid[row][col]\n",
    "        borders = []\n",
    "        dfs(row, col, original)\n",
    "        for x, y in borders:\n",
    "            grid[x][y] = color\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        a = [[False]*n for _ in range(m)]\n",
    "\n",
    "        border = []\n",
    "        ori_color = grid[row][col]\n",
    "\n",
    "        a[row][col]=True\n",
    "        def dfs(x,y):\n",
    "            isborder=False\n",
    "            dirs = [[-1,0],[1,0],[0,1],[0,-1]]\n",
    "\n",
    "            for dx,dy in dirs:\n",
    "                nx,ny=x+dx,y+dy\n",
    "                if not (0<=nx<m and 0<=ny<n and grid[nx][ny]==ori_color):\n",
    "                    isborder = True\n",
    "                    \n",
    "                else:\n",
    "                    if not a[nx][ny]:\n",
    "                        a[nx][ny]=True\n",
    "                        dfs(nx,ny)\n",
    "            if isborder:\n",
    "                border.append([x,y])\n",
    "\n",
    "        dfs(row,col)\n",
    "\n",
    "        print(border)\n",
    "        for x,y in border:\n",
    "            grid[x][y] = color\n",
    "        \n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        vis = set()\n",
    "        edge = set()\n",
    "        def dfs(x, y, c):\n",
    "            vis.add((x, y))\n",
    "            for (a, b) in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if a < 0 or b < 0 or a >= n or b >= m or grid[a][b] != c:\n",
    "                    edge.add((x, y))\n",
    "                elif (a, b) not in vis:\n",
    "                    dfs(a, b, c)\n",
    "        dfs(row, col, grid[row][col])\n",
    "        for x, y in edge:\n",
    "            grid[x][y] = color\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        original = grid[row][col]\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        needChange = [[False] * cols for _ in range(rows)]\n",
    "\n",
    "        def inArea(x, y):\n",
    "            return 0 <= x < rows and 0 <= y < cols\n",
    "\n",
    "        def is_inBorder(x, y):\n",
    "            if x == 0 or x == rows - 1 or y == 0 or y == cols - 1:\n",
    "                return True\n",
    "            for offsetX, offsetY in offsets:\n",
    "                newX, newY = x + offsetX, y + offsetY\n",
    "                if grid[newX][newY] != original:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if is_inBorder(x, y):\n",
    "                needChange[x][y] = True\n",
    "            visited[x][y] = True\n",
    "\n",
    "            for offsetX, offsetY in offsets:\n",
    "                newX, newY = x + offsetX, y + offsetY\n",
    "                if inArea(newX, newY) \\\n",
    "                        and grid[newX][newY] == original \\\n",
    "                        and not visited[newX][newY]:\n",
    "                    visited[newX][newY] = True\n",
    "                    dfs(newX, newY)\n",
    "\n",
    "        dfs(row, col)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if needChange[i][j]:\n",
    "                    grid[i][j] = color\n",
    "\n",
    "        # print(grid)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        vis = set()\n",
    "        def dfs(x, y, c):\n",
    "            vis.add((x, y))\n",
    "            isBorder = False\n",
    "            for (a, b) in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if a < 0 or b < 0 or a >= n or b >= m or grid[a][b] != c:\n",
    "                    isBorder = True\n",
    "            for (a, b) in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0<=a<n and 0<=b<m and (a, b) not in vis and grid[a][b] == c:\n",
    "                    dfs(a, b, c)\n",
    "            if isBorder: grid[x][y] = color\n",
    "        dfs(row, col, grid[row][col])\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        # directions for DFS\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        \n",
    "        original_color = grid[row][col]\n",
    "        border_cells = []\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if not (0 <= i < m) or not (0 <= j < n) or grid[i][j] != original_color or visited[i][j]:\n",
    "                return \n",
    "            \n",
    "            visited[i][j] = True\n",
    "            \n",
    "            # if the cell is on the border or next to a cell of a different color, it is a border cell\n",
    "            if i == 0 or i == m-1 or j == 0 or j == n-1 or any(grid[i+dx][j+dy] != original_color for dx, dy in directions if 0 <= i+dx < m and 0 <= j+dy < n):\n",
    "                border_cells.append((i, j))\n",
    "                \n",
    "            for dx, dy in directions:\n",
    "                dfs(i+dx, j+dy)\n",
    "            \n",
    "           \n",
    "        \n",
    "        dfs(row, col)\n",
    "        \n",
    "        # paint the border cells\n",
    "        for i, j in border_cells:\n",
    "            grid[i][j] = color\n",
    "        \n",
    "        return grid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, G: List[List[int]], r: int, c: int, C: int) -> List[List[int]]:\n",
    "        X, book = G[r][c], set()\n",
    "        def dfs(r, c):\n",
    "            if (r, c) in book: return 1\n",
    "            if r in (-1, len(G)) or c in (-1, len(G[0])) or G[r][c] != X: return 0\n",
    "            else: book.add((r, c))\n",
    "            if sum(dfs(r + dr, c + dc) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))) != 4: G[r][c] = C\n",
    "            return 1\n",
    "        dfs(r, c)\n",
    "        return G\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        image=grid\n",
    "        sr=row\n",
    "        sc=col\n",
    "        ret=copy.deepcopy(image)\n",
    "        m,n=len(image),len(image[0])\n",
    "        d=[[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        st=image[sr][sc]\n",
    "        find=set()\n",
    "        def dfs(x,y,st,c):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return\n",
    "            if (x,y) in find:\n",
    "                return \n",
    "            find.add((x,y)) \n",
    "            if image[x][y]!=st:\n",
    "                return\n",
    "            mark=False\n",
    "            for a,b in d:\n",
    "                xx,yy=x+a,y+b\n",
    "                if xx<0 or yy<0 or xx>=m or yy>=n:\n",
    "                    mark=True\n",
    "                elif image[xx][yy]!=st:\n",
    "                    mark=True\n",
    "                if mark:\n",
    "                    ret[x][y]=c\n",
    "                dfs(a+x,b+y,st,c)\n",
    "        dfs(sr,sc,st,color)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        tac=grid[row][col]\n",
    "        rds=[(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        visited=[[False for i in range(n)] for j in range(m)]\n",
    "        def dfs(x,y):\n",
    "            visited[x][y]=True\n",
    "            if 0==x or x==m-1 or 0==y or y==n-1:\n",
    "                ans.append((x,y))\n",
    "            else:\n",
    "                if grid[x+1][y]!=tac or grid[x-1][y]!=tac or grid[x][y+1]!=tac or grid[x][y-1]!=tac:\n",
    "                    ans.append((x,y)) \n",
    "            for i,j in rds:\n",
    "                nx,ny=i+x,y+j\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]==tac and visited[nx][ny]==False:\n",
    "                    dfs(nx,ny)\n",
    "        ans=[]\n",
    "        dfs(row,col)\n",
    "        print(ans)\n",
    "        for i,j in ans:\n",
    "            grid[i][j]=color\n",
    "        return grid"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
